上回將結點架構給設計完畢了,接著我們要來將一些會重複用到的功能設計成函式,這樣可以讓我們的程式變得簡潔,可讀性也會變得更高。
第一個函式用來判斷是否為終點。設計概念為若右岸的傳教士數和食人族數皆為0,並且A船和B船中至少有一艘位於左岸。
設計結果如下:
# Determine whether the state reach the goal
def isGoal(x):
if x.m == 0 and x.c == 0 and (x.a == 0 or x.b == 0):
return True
else:
return False
第二個函式用來確認結點是否在open list之中。每當我們做完結點的展開後,新生成的結點就要放進open list中,之後再根據g值,從最小值者開始進行展開。若展開的結點已經位於open list中,則我們需要確認原先的g值比較小還是新展開的比較小,最終取較小值。
設計結果如下:
# Determine whether the state is in the Open List
def inOpen(x, open):
for e in open:
if x.m == e.m and x.c == e.c and x.a == e.a and x.b == e.b:
return True
return False
第三個函式用來確認新展開的結點是否合法。由於我們的展開方式是直接增減人數並未考慮會不會小於0或是超出原本的人數,因此額外設計此函式來確認是否結點合法,若合法才會新增進list中。
設計結果如下:
# Determine whether the state is legal
def isLegal(bank, boat):
flag1 = flag2 = flag3 = False
if bank.m >= 0 and bank.m <= M and bank.c >= 0 and bank.c <= C:
if bank.m == 0 or bank.m >= bank.c:
flag1 = True
if boat.am >= boat.ac and boat.bm >= boat.bc:
flag2 = True
if M - bank.m >= C - bank.c:
flag3 = True
return flag1 and flag2 and flag3
第四個函式用來將最終的最短路徑結果從closed list中提取出來。提取的方式就利用到了我們一開始設計結點架構時所保留的編號以及父結點編號,從最後的終點一路回推至起點,如此便得到了這條最佳路徑。
設計結果如下:
# conclude the closed_list to result
def showResult(list):
result = []
temp = list[-1]
result.append(temp)
while True:
for e in list:
if e.num == temp.parent:
temp = e
break
result.append(temp)
if temp.num == 0:
break
return result
最後一個函式用來設計heuristic function。我們最終的目標是使用者可以選擇使用A*演算法或是Dijkstra演算法去做推導,因此我們此處將版本一設定為A*演算法,版本二設定為Dijkstra演算法,當使用Dijkstra演算法時,heuristic function就設為0。但目前這裡我們做保留將回傳直接設為0,也就是先皆使用Dijkstra演算法,heuristic的設計可以有許多種可能的,只要能夠是低估或相等於真實的剩餘距離皆是可以的,這邊留給讀者們自己設計。只要將版本依流程控管部分改為自己設計的heuristic函式即可。
設計結果如下:
#Heuristic function
def h(s):
if ("version" == 1):
return 0
else:
return 0
Github連結:https://github.com/Ming06-22/Missionaries-cannibals